/*
无序数组的topK问题，常规思路，类似荷兰国旗问题
 */
/**
 *
 * @param {number[]} arr
 * @param {number} L
 * @param {number} R
 * @return {[]number}
 */
import { swap, randomIndex } from '../sort/utils'

function partition (arr, L, R) {
  const temp = arr[R]
  let less = L - 1
  let more = R + 1
  while (L < more) {
    if (arr[L] > temp) {
      swap(arr, L, --more)
    } else if (arr[L] < temp) {
      swap(arr, L++, ++less)
    } else {
      L++
    }
  }
  return [less + 1, more - 1]
}

/**
 * 第K小的数
 * @param {number[]} arr
 * @param {number} L
 * @param {number} R
 * @param {number} K
 * @return {number}
 */
function find (arr, L, R, K) {
  if (L === R) {
    return arr[L]
  }
  swap(arr, R, randomIndex(L, R))
  const res = partition(arr, L, R)
  if (res[0] > K) {
    return find(arr, L, res[0], K)
  } else if (res[1] < K) {
    return find(arr, res[1], R, K)
  } else {
    return arr[res[0]]
  }
}

function topK (arr, L, R, K) {
  return find(arr, L, R, arr.length - K)
}

const arr = [1, 3, 2, 4, 5, 7, 6, 7]
console.log(topK(arr, 0, arr.length - 1, 4))
